# LeetCode 1049、最后一块石头的重量II

# 一、题目描述

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

示例 1：

输入：stones = [2,7,4,1,8,1] 输出：1 解释：组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

示例 2：

输入：stones = [31,26,33,21,40] 输出：5

提示：

1 <= stones.length <= 30
1 <= stones[i] <= 100

# 二、题目解析

# 三、参考代码

# 1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 微信：wzb_3377
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 最后一块石头的重量II（LeetCode 1049）：https://leetcode.cn/problems/last-stone-weight-ii/submissions/
class Solution {
    public int lastStoneWeightII(int[] stones) {

        // 在两块石头碰撞过程中，可以每次把大的石头划分到 A 部分，小的石头划分到 B 部分
        // 因此可以将数组分成 A 和 B 两个部分
        // A 部分的石头可以被部分留下
        // B 部分的石头全部被粉碎

        // 接下来就是需要思考到底哪些石头放入 A 部分，哪些石头放入 B 部分
        // 其中 A 部分的石头重量和是 sumA
        // 其中 B 部分的石头重量和是 sumB
        // 为了使得最后剩下的石头尽可能的小，那么总是会想去构造 { a , b } 这两个石头的差值尽可能的小
        // 于是问题就变成了：从 stones 中选择一些元素，总和不超过 sum / 2 的最大值

        // 先去计算总和
        int sum = 0;

        for (int num : stones) {

            sum += num;

        }

        int target = sum / 2;

        // dp[i][j] 代表考虑前 i 个物品（数值），凑成总和不超过 j 的最大价值
        int dp[][] = new int[stones.length + 1][target + 1];

        // 01 背包问题开始填充二维数组
        for( int i = 1 ; i <= stones.length  ; i++){

            for( int j = 0 ; j <= target ; j++){

                // 注意到 i 是从下标 1 开始访问的
                // 1、背包容量小于当前元素
                // 背包无法放入 stones[i - 1]
                if ( j < stones[i - 1]){

                    dp[i][j] = dp[ i - 1 ][j];

                // 2、背包容量大于等于当前元素
                // 背包可以放入 stones[i - 1]
                }else{

                    // 不选：方案数为 dp[i - 1][j]
                    // 选：方案数为 dp[i - 1][j - stones[i - 1]] + stones[i-1]
                    dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j - stones[i-1]] + stones[i-1]);
                }
            }
        }
       
        // 这两个部分最大值是 dp[stones.length][target]，剩余的部分就是剩下的石头
        return Math.abs(sum - dp[stones.length][target] - dp[stones.length][target]);

    }
}

# 滚动数组代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 微信：wzb_3377
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 最后一块石头的重量II（LeetCode 1049）：https://leetcode.cn/problems/last-stone-weight-ii/submissions/
class Solution {
    public int lastStoneWeightII(int[] stones) {

        // 在两块石头碰撞过程中，可以每次把大的石头划分到 A 部分，小的石头划分到 B 部分
        // 因此可以将数组分成 A 和 B 两个部分
        // A 部分的石头可以被部分留下
        // B 部分的石头全部被粉碎

        // 接下来就是需要思考到底哪些石头放入 A 部分，哪些石头放入 B 部分
        // 其中 A 部分的石头重量和是 sumA
        // 其中 B 部分的石头重量和是 sumB
        // 为了使得最后剩下的石头尽可能的小，那么总是会想去构造 { a , b } 这两个石头的差值尽可能的小
        // 于是问题就变成了：从 stones 中选择一些元素，总和不超过 sum / 2 的最大值

        // 先去计算总和
        int sum = 0;

        for (int num : stones) {

            sum += num;

        }

        int target = sum / 2;

        // dp[i][j] 代表考虑前 i 个物品（数值），凑成总和不超过 j 的最大价值
        int dp[] = new int[target + 1];

        // 01 背包问题开始填充二维数组
        for( int i = 1 ; i <= stones.length  ; i++){

            for( int j = target ; j >= 0 ; j--){

                // 注意到 i 是从下标 1 开始访问的
                if ( j >= stones[i - 1]){

                     dp[j] = Math.max(dp[j] , dp[j - stones[i-1]] + stones[i-1]);

                }
            }
        }
       
        // 这两个部分最大值是 dp[stones.length][target]，剩余的部分就是剩下的石头
        return Math.abs(sum - dp[target] - dp[target]);

    }
}

# 2、C++ 代码

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {

        // 在两块石头碰撞过程中，可以每次把大的石头划分到 A 部分，小的石头划分到 B 部分
        // 因此可以将数组分成 A 和 B 两个部分
        // A 部分的石头可以被部分留下
        // B 部分的石头全部被粉碎

        // 接下来就是需要思考到底哪些石头放入 A 部分，哪些石头放入 B 部分
        // 其中 A 部分的石头重量和是 sumA
        // 其中 B 部分的石头重量和是 sumB
        // 为了使得最后剩下的石头尽可能的小，那么总是会想去构造 { a , b } 这两个石头的差值尽可能的小
        // 于是问题就变成了：从 stones 中选择一些元素，总和不超过 sum / 2 的最大值

        // 先去计算总和
        int sum = accumulate(stones.begin(), stones.end(), 0);

        int target = sum / 2;

        // dp[i][j] 代表考虑前 i 个物品（数值），凑成总和不超过 j 的最大价值
        vector<vector<int>> dp(stones.size() + 1, vector<int>(target + 1));

        // 01 背包问题开始填充二维数组
        for( int i = 1 ; i <= stones.size()  ; i++){

            for( int j = 0 ; j <= target ; j++){

                // 注意到 i 是从下标 1 开始访问的
                // 1、背包容量小于当前元素
                // 背包无法放入 stones[i - 1]
                if ( j < stones[i - 1]){

                    dp[i][j] = dp[ i - 1 ][j];

                // 2、背包容量大于等于当前元素
                // 背包可以放入 stones[i - 1]
                }else{

                    // 不选：方案数为 dp[i - 1][j]
                    // 选：方案数为 dp[i - 1][j - stones[i - 1]] + stones[i-1]
                    dp[i][j] = max(dp[i-1][j] , dp[i-1][j - stones[i-1]] + stones[i-1]);
                }
            }
        }
       
        // 这两个部分最大值是 dp[stones.length][target]，剩余的部分就是剩下的石头
        return abs(sum - dp[stones.size()][target] - dp[stones.size()][target]);

    }
};

# 3、Python 代码

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        # 在两块石头碰撞过程中，可以每次把大的石头划分到 A 部分，小的石头划分到 B 部分
        # 因此可以将数组分成 A 和 B 两个部分
        # A 部分的石头可以被部分留下
        # B 部分的石头全部被粉碎

        # 接下来就是需要思考到底哪些石头放入 A 部分，哪些石头放入 B 部分
        # 其中 A 部分的石头重量和是 sumA
        # 其中 B 部分的石头重量和是 sumB
        # 为了使得最后剩下的石头尽可能的小，那么总是会想去构造 { a , b } 这两个石头的差值尽可能的小
        # 于是问题就变成了：从 stones 中选择一些元素，总和不超过 sum / 2 的最大值

        # 先去计算总和
        total = sum(stones)

        target = total // 2

        # dp[i][j] 代表考虑前 i 个物品（数值），凑成总和不超过 j 的最大价值
        dp = [[0] * (target + 1) for _ in range(len(stones) + 1)]

        # 01 背包问题开始填充二维数组
        for i in range( 1 , len(stones) + 1 ) :

            for j in range( target + 1):
            

                # 注意到 i 是从下标 1 开始访问的
                # 1、背包容量小于当前元素
                # 背包无法放入 stones[i - 1]
                if  j < stones[i - 1] :

                    dp[i][j] = dp[ i - 1 ][j]

                # 2、背包容量大于等于当前元素
                # 背包可以放入 stones[i - 1]
                else:

                    # 不选：方案数为 dp[i - 1][j]
                    # 选：方案数为 dp[i - 1][j - stones[i - 1]] + stones[i-1]
                    dp[i][j] = max(dp[i-1][j] , dp[i-1][j - stones[i-1]] + stones[i-1])
   
       
        # 这两个部分最大值是 dp[stones.length][target]，剩余的部分就是剩下的石头
        return total - 2*dp[len(stones)][target] 
# 滚动数组
class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        # 在两块石头碰撞过程中，可以每次把大的石头划分到 A 部分，小的石头划分到 B 部分
        # 因此可以将数组分成 A 和 B 两个部分
        # A 部分的石头可以被部分留下
        # B 部分的石头全部被粉碎

        # 接下来就是需要思考到底哪些石头放入 A 部分，哪些石头放入 B 部分
        # 其中 A 部分的石头重量和是 sumA
        # 其中 B 部分的石头重量和是 sumB
        # 为了使得最后剩下的石头尽可能的小，那么总是会想去构造 { a , b } 这两个石头的差值尽可能的小
        # 于是问题就变成了：从 stones 中选择一些元素，总和不超过 sum / 2 的最大值

        # 先计算总和
        sum = 0
        for num in stones:
            sum += num

        target = sum // 2

        # dp[i] 代表考虑前 i 个物品（数值），凑成总和不超过 target 的最大价值
        dp = [0] * (target + 1)

        # 01 背包问题开始填充一维数组
        for i in range(1, len(stones) + 1):
            for j in range(target, -1, -1):
                # 注意到 i 是从下标 1 开始访问的
                if j >= stones[i - 1]:
                    dp[j] = max(dp[j], dp[j - stones[i - 1]] + stones[i - 1])

        # 这两个部分最大值是 dp[len(stones)][target]，剩余的部分就是剩下的石头
        return abs(sum - dp[target] - dp[target])

← LeetCode 337、打家劫舍III LeetCode 416、分割等和子集 →